package part1.q2;

import java.util.Stack;

/**
 * 逆序操作一个栈
 *  【注意 ： 】 只能使用递归函数和栈，不能使用其他的数据结构
 * @author lenovo
 *
 */
public class ReverseStack {
	
	/**
	 * 获取栈底元素，并且将这个元素从栈中移除
	 * @param stack
	 * @return
	 */
	public static int getAndRemoveLsatElement(Stack<Integer> stack) {
		int result = stack.pop();
		// 递归结束的条件
		if(stack.isEmpty()) {
			return result;
		} else {
			// 递归调用
			int last = getAndRemoveLsatElement(stack);
			stack.push(result);
			return last;
		}
		
	}
	
	
	/**
	 * 对栈进行反转，将下面的元素先拿出来，
	 * 然后递归到栈顶的元素，将栈顶的元素重新压入到栈
	 * @param stack
	 */
	public static void reverse(Stack<Integer> stack) {
		if(stack.isEmpty()) {
			return;
		}
		int i = getAndRemoveLsatElement(stack);
		// 一直递归下去，会将栈顶的元素取出来，到栈顶的元素之后又，递归就会跳出来
	    reverse(stack);
	    // 递归跳出来，首先压入栈的就是栈顶的元素
	    stack.push(i);
	}
	
	
	
	
	
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(5);
		
		// System.out.println(getAndRemoveLsatElement(stack));
		reverse(stack);
		
	}
	
	
	
	
}
